package dailyTopic;

/**
 * @author zhangmin
 * @create 2021-08-09 9:54
 *
 * 丑数：1.小顶堆    2.动态规划
 */
public class nthUglyNumber264 {
 /*   public int nthUglyNumber(int n) {
        int[] primes=new int[]{2,3,5};
        //用一个集合来去重
        Set<Long> set=new HashSet<>();
        //用优先队列实现小顶堆
        PriorityQueue<Long> heap=new PriorityQueue<>();
        set.add(1L);
        heap.offer(1L);
        int res=0;
        for (int i = 0; i < n; i++) {
            long now=heap.poll();
            res=(int)now;
            for (int prime:primes) {
                Long temp=now*prime;
                if (set.add(temp))
                    heap.offer(temp);
            }
        }
        return res;
    }*/
    public int nthUglyNumber(int n) {
        int[] ugly=new int[n+1];
        ugly[1]=1;ugly[0]=0;
        int u2=1,u3=1,u5=1;
        for (int i=2;i<n+1;i++){
            ugly[i]=Math.min(Math.min(ugly[u2]*2,ugly[u3]*3),ugly[u5]*5);
            if (ugly[i]==ugly[u2]*2){
                u2++;
            }
            if (ugly[i]==ugly[u3]*3){
                u3++;
            }
            if (ugly[i]==ugly[u5]*5){
                u5++;
            }
        }
        return ugly[n];
    }

    public static void main(String[] args) {
        nthUglyNumber264 object=new nthUglyNumber264();
        System.out.println(object.nthUglyNumber(10));
    }
}
